Sphere decoding complexity exponent for decoding full rate codes over the quasi-static MIMO channel

摘要

In the setting of quasi-static multiple-input multiple-output (MIMO)channels, we consider the high signal-to-noise ratio (SNR) asymptoticcomplexity required by the sphere decoding (SD) algorithm for decoding a largeclass of full rate linear space-time codes. With SD complexity having randomfluctuations induced by the random channel, noise and codeword realizations,the introduced SD complexity exponent manages to concisely describe thecomputational reserves required by the SD algorithm to achieve arbitrarilyclose to optimal decoding performance. Bounds and exact expressions for the SDcomplexity exponent are obtained for the decoding of large families of codeswith arbitrary performance characteristics. For the particular example ofdecoding the recently introduced threaded cyclic division algebra (CDA) basedcodes -- the only currently known explicit designs that are uniformly optimalwith respect to the diversity multiplexing tradeoff (DMT) -- the SD complexityexponent is shown to take a particularly concise form as a non-monotonicfunction of the multiplexing gain. To date, the SD complexity exponent alsodescribes the minimum known complexity of any decoder that can provably achievea gap to maximum likelihood (ML) performance which vanishes in the high SNRlimit.